package controller;

import java.util.ArrayList;
import java.util.TreeMap;

import model.Afd;
import model.Symbol;
import model.Transition;
import model.State;

public class BrzozowskiController {
	private Afd afd;
	private static BrzozowskiController brzozowskiController;
		
	private BrzozowskiController(){
	}
	
	public static BrzozowskiController getInstance(){
		if (brzozowskiController == null) {
			brzozowskiController = new BrzozowskiController();
		}
		return brzozowskiController;
	}
	
	private String getLanguages(State st){
		afd = AfdController.getInstance().getAfd();
		StringBuilder sb = new StringBuilder();
		for (Transition r : afd.getTransitions()) {
			if (r.getInitialState().equals(st)) {
				sb.append("U");
				sb.append(r.getSymbol().toString());
				sb.append("[L" + (afd.getStates().indexOf(r.getFinalState())+1) + "]");
			}
		}
		if (afd.getFinalStates().contains(st)) {
			sb.append("Uɛ");
		}
		sb.deleteCharAt(0);
		return sb.toString();
	}
	
	public String brzozowski(){
		afd = AfdController.getInstance().getAfd();
		TreeMap<String,String> languages = new TreeMap<String,String>(new StringComparator());
		int i = 1;
		for (State st : afd.getStates()) {
			languages.put("[L" + i++ + "]", getLanguages(st));
		}
		i = languages.values().size();
		for (String lang : languages.values()) {
			String regex;
			for (int j = languages.values().size(); j > i; j--) {
				regex = "\\[L" + j + "\\]";
				String tmp;
				if(languages.get("[L"+j+"]").equals("")){
					int index;
					while((index = lang.indexOf("[L"+j+"]"))!=-1){
						lang = lang.replace(lang.charAt(index-1)+"[L"+j+"]", "");
					}
				}
				else{
					tmp = ("(" + languages.get("[L"+j+"]") + ")");
					lang = lang.replaceAll(regex, tmp);
				}
			}
			lang = manipulateLanguage(lang, i);
			languages.put("[L"+i+"]", lang);
			i--;
		}
		return languages.get("[L1]");
	}

	private String manipulateLanguage(String lang, int i) {
		ArrayList<String> list = new ArrayList<String>();
		int l, cont = -1;		
		String regex = ".*\\([^\\(]*\\)\\*.*";
		while (lang.matches(regex)) {
			int j, k;
			for (j = 0, k = lang.length(); j < k && lang.substring(j, k).matches(regex); j++);
			j--;
			for (; j < k && lang.substring(j, k).matches(regex); k--);
			if(k<lang.length())k++;
			String subs = lang.substring(j, k);
			list.add(subs);
			lang = lang.replace(subs, "[S"+(++cont)+"]");
		}
		while((l = lang.indexOf('*'))!= -1){
			char c = lang.charAt(l-1);
			lang = lang.replace(c+"*", "[S"+(++cont)+"]");
			list.add(c+"*");
		}

		lang = distribute(lang);
		lang = sort(lang);
		lang = arden("L"+i, lang);

		for (cont = 0; cont < list.size(); cont++) {
			lang = lang.replace("[S"+cont+"]", list.get(cont));
		}
		
		lang = lang.replaceAll("UUU*", "U");
		lang = lang.replaceAll("\\(\\)", "");
		return lang;
	}

	private String arden(String key, String lang){
		lang = group(key, lang);
		String vet[] = lang.split("\\["+key+"\\]");		

		if(vet.length==1 && (!lang.equals(vet[0])))
			lang = "";
		else if(vet.length > 1){
			if(vet[1].length() > 1){
				vet[1] = vet[1].substring(1);
				if(vet[1].contains("U"))
					vet[1] = "(" +  vet[1] +")";
			}
			lang = vet[0] + "*" + vet[1];
		}
		if(lang.charAt(lang.length()-1)=='ɛ')lang = lang.substring(0,lang.length()-1);
		return lang;
	}

	private String sort(String lang) {
		String vet[];
		String ret = "";
		vet = lang.split("U");
		for (int i = 0; i < vet.length-1; i++) {
			for (int j = i+1; j < vet.length; j++) {
				if (compare(vet[i],vet[j])<0) {
					String aux = vet[i];
					vet[i] = vet[j];
					vet[j] = aux;
				}
			}
		}
		for (String string : vet) {
			ret += "U" + string;
		}

		ret = ret.substring(1);
		return ret;
	}
	
	private String group(String key, String lang){
		String vet[] = lang.split("U");
		String ret = "";
		int i = 0;
		for (String string : vet) {
			if (string.matches(".*\\["+key+"\\]")){
				ret += "U" + string;
				i++;
			}
		}
		if(ret != ""){
			ret = ret.substring(1).replace("["+key+"]", "");
			if(ret.length()>1)
				ret = "(" + ret + ")";
			ret = ret + "[" + key + "]";
		}
		for (;i<vet.length;i++){
			ret += "U" + vet[i];
		}
		if (ret.charAt(0)=='U')
			ret = ret.substring(1);
		return ret;
	}
	
	private int compare(String exp1, String exp2){
		String regex = ".*\\[L\\d+\\]";
		int j, k;
		for (j = 0; exp1.substring(j).matches(regex); j++);
		if(j>0)j--;
		else return -1;
		exp1 = exp1.substring(j);
		for(k = 0; exp2.substring(k).matches(regex); k++);
		if(k>0)k--;
		else return 1;
		exp2 = exp2.substring(k);
		return exp1.compareTo(exp2);
	}

	private String distribute(String lang) {
		String regex = ".*\\([^\\(]*\\).*";
		while(lang.matches(regex)){
			int j, k;
			for (j = 0, k = lang.length(); j < k && lang.substring(j, k).matches(regex); j++);
			if(j<k)j--;
			for (; j < k && lang.substring(j, k).matches(regex); k--);
			int l = 0;
			boolean d = false;
			while(j-l-1>0){
				if(lang.charAt(j-1-l)==')'){
					while(lang.charAt(j-1-l)!='(')l++;
				}
				else if(lang.charAt(j-1-l)==']'){
					while(lang.charAt(j-1-l)!='[')l++;
				}
				else if(afd.getSymbols().contains(new Symbol(lang.charAt(j-1-l)))){
					while(((j-1-l)>=0)&&(afd.getSymbols().contains(new Symbol(lang.charAt(j-1-l)))))l++;
					d = true;
				}
				else break;
			}
			if(d)l--;
			String symbol = lang.substring(j-1-l,j);
			String tmp = lang.substring(j+1, k);
			String vet[] = tmp.split("U");
			tmp = "("+tmp+")";
			String tmp1 = "";
			for (String str : vet) {
				str = symbol + str;
				tmp1 += "U" + str;
			}
			tmp1 = tmp1.substring(1);
			lang = lang.replace(symbol+tmp, tmp1);				
		}
		
		return lang;
	}
	
}